/* CSP-201712P4 行车路线（图、邻接矩阵、最短路、Floyd、SPFA、重边处理）
双向道路，无向图，n最大500，用邻接矩阵可保存。
* 丢分点：
* * 答案不超过10^6，但是边长最大10^5。几条长小路加起来在平方可能超过int32，要用long。
* * 但权值也不能初始化成Long.MAX_VALUE，否则小路权值相加或平方可能溢出。
* * 数据含平行边，而邻接矩阵不支持。当短边在先、长边在后时保留了长边，得90分。建图时要加min。
* 将小路图平方加权合并到大路图思路不通：无法展现连续小路的平方效果。

样例1
6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1
样例输出
76

样例2（选取当前最优、局部最优可能错失全局最优，因此原图不适合贪心策略）
5 5
0 1 2 1
0 1 3 1
1 2 4 2
0 3 4 5
1 4 5 2
样例输出
10
*/
import java.util.*;

public class Main {
  static boolean relax(long[] path, int i, long x){
    if(path[i] > x){ // 尝试用x松弛path[i]
      path[i] = x;
      return true;
    }
    return false;
  }

  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    final int n = s.nextInt(), N = n + 1, m = s.nextInt();
    final long INF = Integer.MAX_VALUE; // 不能用Long.MAX_VALUE，小路权值平方会溢出
    long[][] gB = new long[N][N]; // 大路图（broad）
    long[][] gN = new long[N][N]; // 小路图（narrow）
    for(int i = 0; i < N; ++i) {
      Arrays.fill(gB[i], INF);
      Arrays.fill(gN[i], INF);
    }
    for(int i = 0, t, a, b, c; i < m; ++i) {
      t = s.nextInt(); // 类型
      a = s.nextInt(); // 源点
      b = s.nextInt(); // 端点
      c = s.nextInt(); // 权值
      if(t == 0){ // 大路
        gB[a][b] = gB[b][a] = Math.min(gB[a][b], c); // 重边取最短
      }else{ // 小路
        gN[a][b] = gN[b][a] = Math.min(gN[a][b], c); // 反向边
      }
    }
    // 对小路图用Floyd算法（DP策略）求多源最短路，连通所有小路可达点，相当于把连续小路直连。
    for(int i = 1; i < N; ++i) {
      for(int j = i + 1; j < N; ++j) { // 无向图的邻接矩阵对称，只需算一半，从i+1开始。
        for(int k = 1; k < N; ++k) {
          if(gN[i][j] > gN[i][k] + gN[k][j]) { // 松弛i~j边
            gN[i][j] = gN[j][i] = gN[i][k] + gN[k][j];
          }
        }
      }
    }
    // 用SPFA求大小路组合图
    boolean[] inQ = new boolean[N];
    long[] tireB = new long[N]; // [v]：最后一段走大路抵达点v时的疲劳度
    long[] tireN = new long[N]; // [v]：最后一段走小路抵达点v时的疲劳度
    Arrays.fill(tireB, INF);
    Arrays.fill(tireN, INF);
    ArrayDeque<Integer> q = new ArrayDeque<Integer>(); // 待处理点队列
    q.add(1);
    inQ[1] = true;
    tireB[1] = 0;
    tireN[1] = 0;
    while(!q.isEmpty()) {
      final int u = q.poll();
      inQ[u] = false; // u已出队
      for(int v = 1; v < N; ++v) { // 对u的关联边尝试松弛
        if(relax(tireB, v, Math.min(tireB[u], tireN[u]) + gB[u][v]) && !inQ[v]) {
          q.addLast(v); // ...大路u大路v 或 ...小路u大路v 有更佳路线且v还没入队
          inQ[v] = true;
        }
        if(relax(tireN, v, tireB[u] + gN[u][v] * gN[u][v]) && !inQ[v]) {
          q.addLast(v); // ...大路u小路v。即使上步大路松弛成功也要再检查小路，否则可能漏掉更优解。
          inQ[v] = true;
        }
      }
    }
    System.out.println(Math.min(tireB[n], tireN[n])); // 最优解在两者中
  }
}